package ch09_09;

/**
 * Good Question.
 * Don't forget to call the helper function from entry.
 *
 */
public class Solution {
    public static void printNQueens(int n) {
	int[] colsInEachRow = new int[n];
	/**
	 * Don't forget to call!
	 */
	placeQueens(colsInEachRow, 0);
    }

    private static void placeQueens(int[] colsInRow, int currentRow) {
	int N = colsInRow.length;
	if (currentRow == N) {
	    printBoard(colsInRow);
	    return;
	}
	boolean valid = true;
	for (int j = 0; j < N; j++) {
	    valid = true;
	    for (int i = 0; i < currentRow; i++) {
		if (colsInRow[i] == j ||
		    currentRow - i == Math.abs(colsInRow[i] - j)) {
		    valid = false;
		    break;
		}
	    }
	    if (valid) {
		colsInRow[currentRow] = j;
		placeQueens(colsInRow, currentRow + 1);
	    }
	}
    }

    static int count = 0;
    private static void printBoard(int[] colsInRow) {
    	count++;
	int N = colsInRow.length;
	StringBuffer sb = new StringBuffer();
	sb.append(count + ":\n");
	for (int i = 0; i < N; i++) {
	    for (int j = 0; j < N; j++) {
		if (j == colsInRow[i]) {
		    sb.append('Q');
		} else {
		    sb.append('.');
		}
		sb.append('\t');
	    }
	    sb.append('\n');
	}
	System.out.println(sb.toString());
    }

    public static void main(String... args) {
	int n = 15;
	printNQueens(n);
    }
}